The invention relates to generation of a graph structure for description of an area with a free area and an occupied area.
Repetitious activities are being transferred ever more frequently to service robots. Examples of such activities are cleaning tasks, transport tasks, bringing out grain to the appropriate areas or tasks such as lawn mowing.
To execute the relevant area processing the appropriate area processing equipment such as cleaning equipment or cutting equipment is installed on such service robots.
Efficient processing of the areas by the service robots requires that the area processing device covers the entire area to be processed where possible and does not travel down the same path twice where possible.
This however requires planning of a suitable efficient processing path.
Path planning methods in general require a knowledge of the geometrical circumstances of the area to be processed. This includes for example information about the dimensions of the area to be processed and the positions and dimensions of obstacles within it.
As a rule digital, geometrical maps are used in which the relevant geometrical circumstances of the area to be processed are stored. Such geometrical circumstances appear in these geometrical maps as what are known as free areas, for example obstacle-free and processable surfaces, and also as occupied areas, such as areas occupied by obstacles which cannot be processed.
In concrete terms such geometrical maps correspond to what are known as pixel images of which the pixels are assigned image and/or color information in each case. Such pixel images, such as gray scale maps or color images which are used and/or analyzed and evaluated in image processing and/or object recognition also enable a distinction to be made between free areas and occupied areas.
With the appropriate prior knowledge such a digital geometrical map can be created in advance and stored in a service robot. In this case the path planning method or the path planning can be executed in advance. The path to be traveled is known at the start of area processing.
A digital, geometrical map can also be created dynamically during an actual area processing operation. In this case path planning is undertaken during area processing.
Various methods of generating such geometrical maps are known from Sebastian Thrun, “Robotic Mapping: a Survey”, February 2002 CMU-CS-02-11, in G. Lakemeyer, B. Nebel (eds.), “Exploring AI in the New Millennium”, Chapter 1, Morgan Kaufmann, San Francisco and obtainable from: http://www2.cs.cmu.edu/afs/cs.cmu.edu/user/thrun/public_html/papers/thrun.mapping-tr.html (“the Thrun reference”), A. Elfes, “Occupancy Grids: A Probabilistic Framework for Robot Perception and Navigation”, Department of Electrical and Computer Engineering, Carnegie Mellon University 1989 (“the Elfes reference”), and H. P Moravec, “sensors Fusion in certainty grids for mobile robots”, AI Magazine, 9(2): 61-74, 1988 (“the Moravec reference”).
Path planning methods based on these geometrical maps are also known. Different path planning methods are given as examples below.
So-called template-based methods for full-coverage path planning which use such geometrical maps are known from C. Hofner and G. Schmidt, Path Planning And Guidance Techniques For An Autonomous Mobile Cleaning Robot, International Conference on Intelligent Robots and Systems (IROS), pp. 610-617, 1994, R. Neumann de Carvalho, H. A. Vidal, P. Vieira, and M. I. Ribeiro, Complete Coverage Path Planning and Guidance for Cleaning Robots, IEEE International Symposium on Industrial Electronics, pp. 677-682, 1997, and H. Choset and P. Pignon, Coverage Path Planning: The Boustrophedon Cellular Decomposition, International Conference on Field and Service Robotics, 1997, for example. A further path planning method A. Zelinsky, R. A. Jarvis, J. C. Byarne and S. Yuta, Planning Paths of Complete Coverage of an Unstructered Environment by a Mobile Robot, International Conference on Robotica and Automation (ICRA), pp. 533-538, 1993, which also uses a geometrical digital map, but adopts another approach, uses a potential field, with which an area to be processed is overlaid and a processing path thus determined. Further map-based path planning methods with a similar approach based on geometrical maps are known from E. Prassler, D. Schwammkrug, B. Rohrmoser, and G. Schmidl, Autonomous Road Sweeping of Large Public Areas, Robotik 2000, VDI Reports 1552, VDI Verlag GmbH, Dusseldorf, 2000 and E. Prassler, D. Schwammkrug, B. Rohrmoser, and G. Schmidl, A Robotic Road Sweeper, International Conference on Robotica and Automation (ICRA), pp. 2364-2369, 2000.
As well as being used for determining a processing path, such geometrical maps also serve as the basis for determining the current position or a location of a mobile robot in an area (position estimation). This is referred to as localization or global localization. Furthermore such geometrical maps are also used for orientation and navigation of the robot in an area.
Corresponding methods for localization or global localization, orientation and navigation of mobile robots, based on geometrical maps, are also known, for example from Howie Choset et al., “topology Simultaneous Localization and Mapping (SLAM): Toward Exact Localization Without Explicit Localisation”, S. 125-137, IEEE Transactions on Robotics and Automation, Vol. 17, No. 2, April 2001 (“the Choset et al. reference”).
The disadvantage of these geometrical maps is that they need significant storage space or are dependent on one type of environment. In addition, for relocalization for example, they require long computing times.
Further disadvantages are the effort involved in the creation of such geometrical maps and that the maps themselves are mostly inaccurate, especially in large and/or unstructured environments.
These geometrical maps thus prove to be of only limited use for the localization of robots in dynamically changing environments Current environments and in some cases those which are subject to just short-term changes, such as a person being in the area, or shelving and such like temporarily placed in the area lead to changed current local section maps, i.e. to changes in the free areas and the occupied areas, and, because of the changes, these sectional maps can only be reflected with difficulty in the geometrical (basic) map.
As a rule this requires time-consuming and memory-intensive correlation procedures. Feature-based search procedures fail if environment elements are changed in such a way that, because they are covered up they can no longer be recognized.
The same problem arises not only in the interpretation of the pixel images as geometrical maps but also for object detection in color images or gray scale maps.
In addition to such geometrical maps, topological maps are also known for localization and navigation of mobile robots in an area.
These topological maps use a graph or a graph structure to describe an area which as a rule is generated from a contiguous sequence of nodes and connectors.
So-called Voronoi Graphs (VG) or Generalized Voronoi Graphs (GVG) the Choset et al. reference, D. Van Zwynsvoorde et al., “Incremental topology Modeling using Local Voronoi-like Graphs”, Paper Submitted to IEEE Int. Conf. On Intelligent Robots and Systems, 2000 (“the Zwynsvoorde et al. Incremental topology reference”), D. Van Zwynsvoorde et al., “Building topology models for navigation in large scale environments”, LAAS-CNRS, Toulouse, France, 2001 (“the Zwynsvoorde et al. Builing topology reference”) as well as the “medial axis” are known examples of these kinds of topologically used or “topological” graphs or graph structures Philip N. Klein et al., “Shape matching using editdistance: an implementation”, Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001, Dept. of Computer Science, Brown Universitiy, Providence (“the Klein et al. reference”), the Choset et al. reference. The “medial axis” (MA) is formed in this case by the locations or the set of circle center points of all circles of a maximum size which lie completely within the enclosed area and touch at least twice.
However these topological graphs only describe free parts of an area, they do not explicitly describe the occupied area or the obstacles in the area and do not describe these in a form such as would make it possible to reproduce the obstacles.
The free areas are described structurally and not metrically in such cases by the graphs, i.e. more precise geometrical information about the area, such as distances or dimensions for obstacles cannot be taken from the graphs as a rule.
Therefore such “topological” graphs, such as Voronoi graphs or medial axis, have only limited suitability for localization or global localization, orientation or navigation of a mobile robot.
A Shock Graph (SG) is known from the Klein et al. reference which is used in this document in image processing or object detection for structural description of areas and shapes enclosed by outlines.